package leetcode._06_回溯;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/3 9:27
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * <p>
 * 示例 1：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * <p>
 * 示例 2：
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * <p>
 * 示例 3：
 * 输入：nums = [1]
 * 输出：[[1]]
 */
public class _46_全排列 {

    @Test
    public void T_review() {
        int[] nums = {1, 2, 3,4};
        // int[] nums = {1,2,2};
        // int[] nums = {1};
        List<List<Integer>> permute = permute_review(nums);
        System.out.println();
    }
    public List<List<Integer>> permute_review(int[] nums) {
        Arrays.sort(nums);
        ArrayList<Integer> nList = new ArrayList<>();
        for (int num : nums) {
            nList.add(num);
        }
        dfs_review(0,nList);
        return res;
    }

    private void dfs_review(int i, ArrayList<Integer> nums) {
        if(i == nums.size()){
            res.add(new ArrayList<>(path));
            return;
        }

        for (int j = i; j < nums.size(); j++) {
            if(j > i && (nums.get(j-1).equals(nums.get(j)))){
                continue;
            }
            path.add(nums.get(j));
            Collections.swap(nums,i,j);

            dfs_review(i+1,nums);
            Collections.swap(nums,i,j);
            path.removeLast();
        }
    }

    @Test
    public void T_() {
        // int[] nums = {1, 2, 3,4};
        int[] nums = {0,1};
        // int[] nums = {1};
        List<List<Integer>> permute = permute2(nums);
        System.out.println();
    }
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    /*s1:回溯全排*/
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length == 0){
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        dfs(list);
        return res;
    }

    private void dfs(ArrayList<Integer> list) {
        if(list.size() == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < list.size(); i++) {
            path.add(list.get(i));
            ArrayList<Integer> t = new ArrayList<>(list);
            t.remove(i);
            dfs(t);
            path.removeLast();
        }
    }

    /*s2:动态规划*/
    public List<List<Integer>> permute2(int[] nums){
        dfs2(nums,0);
        return res;
    }

    /*在不重复的数组中的所有空白位置插入下一个数字*/
    private void dfs2(int[] nums,int beginIndex) {
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = beginIndex; i < nums.length; i++) {
            for (int j = 0; j <= path.size(); j++) {
                path.add(j,nums[i]);
                dfs2(nums,i+1);
                path.remove(j);
            }
        }
    }

    /*官方题解--将数组划分为使用过的数据和未使用过的数据，交换两个数据*/
    public List<List<Integer>> permuteGF(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }

}

